package com.dyz.LeetCodeforSwordFingerOffer;

import java.util.ArrayList;
import java.util.List;

public class PathSum34 {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if(root==null){
            return res;
        }
        ArrayList<Integer> path = new ArrayList<>();
        dfs(root, target, path);
        return res;
    }
    private void dfs(TreeNode root, int target, ArrayList<Integer> path){
        if(root == null){
            return;
        }
        path.add(root.val);
        target -= root.val;
        // 必须是叶子节点才行
        if(target==0 && root.left==null && root.right==null){
            List<Integer> tmp = new ArrayList<>(path);
            res.add(tmp);
        }
        dfs(root.left, target, path);
        dfs(root.right,target, path);
        path.remove(path.size()-1); //注意：记得回溯时一定要移除每次递归添加的元素，保证每次递归都是独立的。
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(-2);
        TreeNode right = new TreeNode(-3);
        root.right = right;
        List<List<Integer>> lists = new PathSum34().pathSum(root, -5);
        System.out.println(lists);
    }
}
